# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/9/23
# @File : 9.E - Crested Ibis vs Monster（打怪兽，第二次做）.py


def dp_WQ_2Beibao(a,b,h,n):
    dp = [[100000000]*(h+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 0
    for i in range(1,n+1):
        for j in range(1,h+1):
            dp[i][j]=min(dp[i-1][j],dp[i][max(j-a[i],0)]+b[i])
    return dp[-1][-1]

def dp_WQ_2Beibao_one_array(a,b,h,n):
    dp = [100000000]*(h+1)
    dp[0] = 0
    for i in range(1,n+1):
        for j in range(1,h+1):
            dp[j]=min(dp[j],dp[max(j-a[i],0)]+b[i])
    return dp[-1]
"""
完全背包加可以大于怪物能量，一维数组是顺序（非逆序）
就比如现在的技能i 可以造成伤害为3， 现在的j值为 2  你一样可以动用这技能造成怪物2点伤害（然后还多了一个点），所以这里就不能直接等于dp[i-1][j]，也要用上这个b[i]（自身输出）来作比较看谁小。
"""
if __name__ == "__main__":
    h,n = map(int ,input().split())
    a = [0]
    b = [0]
    for _ in range(n):
        rate = [int(i) for i in input().split()]
        a.append(rate[0])
        b.append(rate[1])
    print(dp_WQ_2Beibao_one_array(a,b,h,n))